package array.medium;

/**
 * 搜索二维矩阵
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 *
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 */
public class SearchA2DMatrix_74 {

    public boolean searchMatrix(int[][] matrix, int target) {

        int l = 0, r = matrix.length - 1;
        while (l < r) {
            int mid = l + (r + 1) >> 1;
            if (matrix[mid][0] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        int row = r;
        if (matrix[row][0] == target)
            return true;
        if (matrix[row][0] > target)
            return false;

        l = 0;
        r = matrix[0].length - 1;
        while(l < r) {
            int mid = l + (r + 1) >> 1;
            if (matrix[row][mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        int col = r;


        return matrix[row][col] == target;
    }

    public static void main(String[] args) {
        SearchA2DMatrix_74 sa = new SearchA2DMatrix_74();
        System.out.println(sa.searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}}, 13));
    }
}
